package com.cat.binaryTree;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/most-frequent-subtree-sum/https://leetcode.cn/problems/most-frequent-subtree-sum/
 * @create 2025/9/11 23:08
 * @since JDK17
 */

public class Solution21 {
    int max;
    Map<Integer, Integer> map = new HashMap<>();
    int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = root.val + dfs(root.left);
        int right = root.val + dfs(root.right);
        map.merge(left + right, 1, Integer::sum);
        max = Math.max(max, map.get(left + right));
        return left + right;
    }

    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        List<Integer> ans = new ArrayList<>();
        for (Integer num : map.keySet()) {
            if (map.get(num) == max) {
                ans.add(num);
            }
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
